#include <deque>
#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

class Solution {
public:
  vector<vector<int>> levelOrder(TreeNode *root) {
    if (!root)
      return {};
    std::deque<TreeNode *> tmpQue;
    TreeNode *pNextHead = nullptr;
    std::vector<std::vector<int>> res;
    std::vector<int> tmp;

    tmpQue.push_back(root);

    while (!tmpQue.empty()) {
      TreeNode *p = tmpQue.front();
      if (p == pNextHead) {
        res.push_back(tmp);
        tmp.clear();
        pNextHead = nullptr;
      }
      if (p->left != nullptr) {
        tmpQue.push_back(p->left);
        if (pNextHead == nullptr) {
          pNextHead = p->left;
        }
      }
      if (p->right != nullptr) {
        tmpQue.push_back(p->right);
        if (pNextHead == nullptr) {
          pNextHead = p->right;
        }
      }
      tmp.push_back(p->val);
      tmpQue.pop_front();
    }
    if (!tmp.empty()) {
      res.push_back(tmp);
    }
    return res;
  }
};
